package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
106.从中序与后序遍历序列构造二叉树
 */
public class Of20210320LeetCode106 {
    /*
    根据一棵树的中序遍历与后序遍历构造二叉树。
    注意: 你可以假设树中没有重复的元素。
     */
    public static void main(String[] args) {
        System.out.println(buildTree(Arrays.asList(9, 3, 15, 20, 7), Arrays.asList(9, 15, 7, 20, 3)));
    }

    /*
    第一步：如果数组大小为零的话，说明是空节点了。
    第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
    第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
    第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
    第五步：切割后序数组，切成后序左数组和后序右数组
    第六步：递归处理左区间和右区间
     */
    private static TreeNode traversal (List<Integer> inorder, int inorderBegin, int inorderEnd, List<Integer> postorder, int postorderBegin, int postorderEnd) {

        if (postorderBegin == postorderEnd) return null;

        int rootValue = postorder.get(postorderEnd - 1);
        TreeNode root = new TreeNode(rootValue);

        if (postorderEnd - postorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder.get(delimiterIndex) == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + delimiterIndex - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (delimiterIndex - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root.left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root.right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
    private static TreeNode buildTree(List<Integer> inorder, List<Integer> postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return null;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
}
